// 224. 基本计算器
package Leetcode_Second_Brush;

import java.util.Deque;
import java.util.LinkedList;

public class Solution224 {
    public int calculate(String s) {
        Deque<Integer> nums = new LinkedList<>();
        Deque<Character> ops = new LinkedList<>();
        nums.push(0); // 初始化栈，避免负数的特殊处理

        s = s.replaceAll("\\s+", "").replaceAll("\\(-", "(0-").replaceAll("\\(\\+", "(0+");

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 如果遇到数字，则可能是多位
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                i--; // 调整索引
                nums.push(num);
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    nums.push(operate(nums.pop(), nums.pop(), ops.pop()));
                }
                ops.pop(); // 弹出 '('
            } else { // 处理 + 和 -
                while (!ops.isEmpty() && ops.peek() != '(') {
                    nums.push(operate(nums.pop(), nums.pop(), ops.pop()));
                }
                ops.push(c);
            }
        }

        while (!ops.isEmpty()) {
            nums.push(operate(nums.pop(), nums.pop(), ops.pop()));
        }

        return nums.pop();
    }

    private int operate(int b, int a, char op) {
        if (op == '+')
            return a + b;
        if (op == '-')
            return a - b;
        return 0;
    }

}
